{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Incompatibility"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumIncompatibility"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小不兼容性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code>​​​ 和一个整数 <code>k</code> 。你需要将这个数组划分到 <code>k</code> 个相同大小的子集中，使得同一个子集里面没有两个相同的元素。</p>\n",
    "\n",
    "<p>一个子集的 <strong>不兼容性</strong> 是该子集里面最大值和最小值的差。</p>\n",
    "\n",
    "<p>请你返回将数组分成 <code>k</code> 个子集后，各子集 <strong>不兼容性 </strong>的<strong> 和</strong> 的 <strong>最小值</strong> ，如果无法分成分成 <code>k</code> 个子集，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>子集的定义是数组中一些数字的集合，对数字顺序没有要求。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,1,4], k = 2\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>最优的分配是 [1,2] 和 [1,4] 。\n",
    "不兼容性和为 (2-1) + (4-1) = 4 。\n",
    "注意到 [1,1] 和 [2,4] 可以得到更小的和，但是第一个集合有 2 个相同的元素，所以不可行。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [6,3,8,1,3,1,2,2], k = 4\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>最优的子集分配为 [1,2]，[2,3]，[6,8] 和 [1,3] 。\n",
    "不兼容性和为 (2-1) + (3-2) + (8-6) + (3-1) = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [5,3,3,6,3,3], k = 3\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>没办法将这些数字分配到 3 个子集且满足每个子集里没有相同数字。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= k <= nums.length <= 16</code></li>\n",
    "\t<li><code>nums.length</code> 能被 <code>k</code> 整除。</li>\n",
    "\t<li><code>1 <= nums[i] <= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-incompatibility](https://leetcode.cn/problems/minimum-incompatibility/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-incompatibility](https://leetcode.cn/problems/minimum-incompatibility/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1,4]\\n2', '[6,3,8,1,3,1,2,2]\\n4', '[5,3,3,6,3,3]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        groupsize = len(nums)//k\n",
    "        maxdiff = max(nums)-min(nums)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def minDiff(nums):\n",
    "            if not nums: return 0\n",
    "            ans = maxdiff*k+1\n",
    "            for group in combinations(nums, groupsize):\n",
    "                if len(set(group)) < groupsize: continue\n",
    "                left = list(nums)\n",
    "                for num in group: left.remove(num)\n",
    "                ans = min(ans, max(group)-min(group)+minDiff(tuple(left)))\n",
    "            return ans\n",
    "        \n",
    "        diff = minDiff(tuple(nums))\n",
    "        return diff if diff<maxdiff*k+1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "    n = len(nums)\n",
    "    subsetSize = int(n / k)\n",
    "    numCounts = [0] * (n + 1)\n",
    "    for num in nums:\n",
    "      numCounts[num] += 1\n",
    "    minScore = math.inf\n",
    "\n",
    "    def backtrack(involvedNumsCount, currentScore, lastNum):\n",
    "      nonlocal minScore\n",
    "\n",
    "      if involvedNumsCount == n:\n",
    "        minScore = currentScore\n",
    "        return\n",
    "\n",
    "      involvedNumsCount += 1\n",
    "      subsetEnd = involvedNumsCount % subsetSize == 0\n",
    "\n",
    "      if lastNum is None:\n",
    "        for num in range(1, n + 2 - subsetSize):\n",
    "          if numCounts[num] == 0:\n",
    "            continue\n",
    "\n",
    "          numCounts[num] -= 1\n",
    "          backtrack(involvedNumsCount, currentScore, None if subsetEnd else num)\n",
    "          numCounts[num] += 1\n",
    "\n",
    "          # Avoids checking same subsets in different order\n",
    "          break\n",
    "      else:\n",
    "        numsLeft = n - involvedNumsCount\n",
    "        # Assuming that the other numbers are adjacent\n",
    "        optimisticRestScore = numsLeft - floor(numsLeft / subsetSize)\n",
    "        \n",
    "        # `lastNum + 1` as the start avoids checking permutations of subsets\n",
    "        for num in range(lastNum + 1, n + 1):\n",
    "          if numCounts[num] == 0:\n",
    "            continue\n",
    "\n",
    "          nextScore = currentScore + num - lastNum\n",
    "          if nextScore + optimisticRestScore >= minScore:\n",
    "            # The next nums will give even bigger score\n",
    "            return\n",
    "\n",
    "          numCounts[num] -= 1\n",
    "          backtrack(involvedNumsCount, nextScore, None if subsetEnd else num)\n",
    "          numCounts[num] += 1\n",
    "    \n",
    "    backtrack(0, 0, None)\n",
    "    return minScore if minScore is not math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: list[int], k: int) -> int:\n",
    "        if max(Counter(nums).values()) > k: return -1\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [[] for _ in range(k)]\n",
    "        vis = [-1] * n\n",
    "        ans = inf\n",
    "        def dfs(pos):\n",
    "            nonlocal ans\n",
    "            if sum(max(x) - min(x) for x in g if x) >= ans:\n",
    "                return\n",
    "            if pos == n:\n",
    "                ans = sum(max(x) - min(x) for x in g)\n",
    "                return\n",
    "            for i in range(k):\n",
    "                if len(g[i]) == m:\n",
    "                    continue\n",
    "                if pos and nums[pos - 1] == nums[pos] and vis[pos - 1] >= i:\n",
    "                    continue\n",
    "                #f pos == 0 or nums[pos - 1] != nums[pos] or vis[pos - 1] < i:\n",
    "                g[i].append(nums[pos])\n",
    "                vis[pos] = i\n",
    "                dfs(pos + 1)\n",
    "                g[i].pop()\n",
    "                vis[pos] = -1\n",
    "                if not g[i]:\n",
    "                    break\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        l = len(nums)\n",
    "        n = l // k\n",
    "        if n == 0 or n == 1: return 0\n",
    "        counter = collections.Counter(nums)\n",
    "        if max(counter.values()) > k: return -1\n",
    "        keys = sorted(counter.keys())\n",
    "        ans = float('inf')\n",
    "        def backtrack(idx, cur_num, cur_list, delta):\n",
    "            nonlocal ans\n",
    "            if delta >= ans: return\n",
    "            if len(cur_list) == n:\n",
    "                delta += cur_list[-1] - cur_list[0]\n",
    "                cur_list = []\n",
    "                cur_num = -1\n",
    "            if idx == l:\n",
    "                ans = min(ans, delta)\n",
    "                return\n",
    "            for i in keys:\n",
    "                if i <= cur_num or counter[i] == 0:\n",
    "                    continue\n",
    "                counter[i] -= 1\n",
    "                cur_list.append(i)\n",
    "                backtrack(idx+1, i, cur_list, delta)\n",
    "                cur_list.pop()\n",
    "                counter[i] += 1\n",
    "                if len(cur_list) == 0:\n",
    "                    break\n",
    "        backtrack(0, -1, [], 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: list[int], k: int) -> int:\n",
    "        if max(Counter(nums).values()) > k: return -1\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [[] for _ in range(k)]\n",
    "        vis = [-1] * n\n",
    "        ans = inf\n",
    "        def dfs(pos):\n",
    "            nonlocal ans\n",
    "            if sum(max(x) - min(x) for x in g if x) >= ans:\n",
    "                return\n",
    "            if pos == n:\n",
    "                ans = sum(max(x) - min(x) for x in g)\n",
    "                return\n",
    "            for i in range(k):\n",
    "                # 满了的跳过\n",
    "                if len(g[i]) == m:\n",
    "                    continue\n",
    "                # 1 2 3 4 如果不是【1，2】【3，4】就会是[1,3][2,4],[1,4][2,3]都不是最优，只有按顺序选才是最优,vis就是控制选择顺序的\n",
    "                if pos and nums[pos - 1] == nums[pos] and vis[pos - 1] >= i:\n",
    "                    continue\n",
    "                #f pos == 0 or nums[pos - 1] != nums[pos] or vis[pos - 1] < i:\n",
    "                g[i].append(nums[pos])\n",
    "                vis[pos] = i\n",
    "                dfs(pos + 1)\n",
    "                g[i].pop()\n",
    "                vis[pos] = -1\n",
    "                # 回溯完了还没选成，直接结束\n",
    "                if not g[i]:\n",
    "                    break\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n, self.k = 0, 0\n",
    "        self.nums, self.visited = [], []\n",
    "        self.ans = float('inf')\n",
    "\n",
    "    @staticmethod\n",
    "    def can_split_k_group(nums, k) -> bool:\n",
    "        num_count_dic = defaultdict(int)\n",
    "        for num in nums:\n",
    "            num_count_dic[num] += 1\n",
    "        for v in num_count_dic.values():\n",
    "            if v > k:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        # -1判断\n",
    "        if not self.can_split_k_group(nums, k): return -1\n",
    "        nums.sort()\n",
    "        self.nums = nums\n",
    "\n",
    "        self.ans = float('inf')\n",
    "        self.n, self.k = len(nums), k\n",
    "        self.visited = [0] * len(nums)\n",
    "\n",
    "        self.visited[0] = 1\n",
    "        self.dfs(0, 1, nums[0], nums[0], 0)\n",
    "        return int(self.ans)\n",
    "\n",
    "    def dfs(self, cur, count, low, high, ans_sum):\n",
    "        if count == self.n // self.k:\n",
    "            j = self.visited.index(0) if 0 in self.visited else self.n\n",
    "            if j == self.n:\n",
    "                self.ans = min(self.ans, ans_sum + high - low)\n",
    "            else:\n",
    "                self.visited[j] = 1\n",
    "                self.dfs(j, 1, self.nums[j], self.nums[j], ans_sum + high - low)\n",
    "                self.visited[j] = 0\n",
    "        else:\n",
    "            last = -1\n",
    "            for i in range(cur + 1, self.n):\n",
    "                if self.visited[i] == 1 or self.nums[i] == self.nums[cur]: continue\n",
    "                if i > cur + 1 and self.nums[i] == last: continue\n",
    "\n",
    "                self.visited[i] = 1\n",
    "\n",
    "                self.dfs(i, count + 1, low, self.nums[i], ans_sum)\n",
    "\n",
    "                last = self.nums[i]\n",
    "                self.visited[i] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        nums.sort()\n",
    "        from collections import Counter\n",
    "        if max(Counter(nums).values()) > k:\n",
    "            return -1\n",
    "        path = [[] for _ in range(k)]\n",
    "        vis = [-1]*n\n",
    "        ans = inf\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if sum(max(p) - min(p) for p in path if p) >= ans:\n",
    "                return\n",
    "            if i == n:\n",
    "                ans = sum(max(p) - min(p) for p in path)\n",
    "                return\n",
    "            for j in range(k):\n",
    "                if len(path[j]) == m:\n",
    "                    continue\n",
    "                if i and nums[i] == nums[i - 1] and vis[i - 1] >= j:\n",
    "                    continue\n",
    "                vis[i] = j\n",
    "                path[j].append(nums[i])\n",
    "                dfs(i + 1)\n",
    "                path[j].pop()\n",
    "                vis[i] = -1\n",
    "                if not path[j]:\n",
    "                    break\n",
    "        dfs(0)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n, self.gp_len = 0, 0\n",
    "        self.nums, self.visited = [], []\n",
    "        self.ans = float('inf')\n",
    "\n",
    "    @staticmethod\n",
    "    def can_split_k_group(nums, k) -> bool:\n",
    "        num_count_dic = defaultdict(int)\n",
    "        for num in nums:\n",
    "            num_count_dic[num] += 1\n",
    "        for v in num_count_dic.values():\n",
    "            if v > k:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        # -1判断\n",
    "        if not self.can_split_k_group(nums, k): return -1\n",
    "        nums.sort()\n",
    "        self.nums = nums\n",
    "\n",
    "        self.ans = float('inf')\n",
    "        self.n, self.gp_len = len(nums), len(nums) // k\n",
    "        self.visited = [0] * len(nums)\n",
    "\n",
    "        self.visited[0] = 1\n",
    "        self.dfs(0, 1, nums[0], nums[0], 0)\n",
    "        return int(self.ans)\n",
    "\n",
    "    def dfs(self, cur, v_cnt, low, high, ans_sum):\n",
    "        if v_cnt == self.gp_len and 0 not in self.visited:\n",
    "            self.ans = min(self.ans, ans_sum + high - low)\n",
    "            return\n",
    "\n",
    "        if v_cnt < self.gp_len:\n",
    "            last = -1\n",
    "            for i in range(cur + 1, self.n):\n",
    "                if self.visited[i] == 1 or self.nums[i] == self.nums[cur]: continue\n",
    "                if i > cur + 1 and self.nums[i] == last: continue\n",
    "\n",
    "                self.visited[i] = 1\n",
    "                self.dfs(i, v_cnt + 1, low, self.nums[i], ans_sum)\n",
    "                last = self.nums[i]\n",
    "                self.visited[i] = 0\n",
    "        else:  # 分完一组\n",
    "            j = self.visited.index(0)\n",
    "\n",
    "            self.visited[j] = 1\n",
    "            self.dfs(j, 1, self.nums[j], self.nums[j], ans_sum + high - low)\n",
    "            self.visited[j] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: list[int], k: int) -> int:\n",
    "        if max(Counter(nums).values()) > k: return -1\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [[] for _ in range(k)]\n",
    "        vis = [-1] * n\n",
    "        ans = 0x3f3f3f3f\n",
    "\n",
    "        def dfs(pos):\n",
    "            nonlocal ans\n",
    "            if sum(max(x) - min(x) for x in g if x) >= ans:\n",
    "                return\n",
    "            if pos == n:\n",
    "                ans = sum(max(x) - min(x) for x in g)\n",
    "                return\n",
    "            for i in range(k):\n",
    "                if len(g[i]) == m:\n",
    "                    continue\n",
    "                if pos == 0 or nums[pos - 1] != nums[pos] or vis[pos - 1] < i:\n",
    "                    g[i].append(nums[pos])\n",
    "                    vis[pos] = i\n",
    "                    dfs(pos + 1)\n",
    "                    g[i].pop()\n",
    "                    vis[pos] = -1\n",
    "                    if not g[i]:\n",
    "                        break\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: list[int], k: int) -> int:\n",
    "        if max(Counter(nums).values()) > k: return -1\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [[] for _ in range(k)]\n",
    "        vis = [-1] * n\n",
    "        ans = inf\n",
    "        def dfs(pos):\n",
    "            nonlocal ans\n",
    "            if sum(max(x) - min(x) for x in g if x) >= ans:\n",
    "                return\n",
    "            if pos == n:\n",
    "                ans = sum(max(x) - min(x) for x in g)\n",
    "                return\n",
    "            for i in range(k):\n",
    "                if len(g[i]) == m:\n",
    "                    continue\n",
    "                if pos == 0 or nums[pos - 1] != nums[pos] or vis[pos - 1] < i:\n",
    "                    g[i].append(nums[pos])\n",
    "                    vis[pos] = i\n",
    "                    dfs(pos + 1)\n",
    "                    g[i].pop()\n",
    "                    vis[pos] = -1\n",
    "                    if not g[i]:\n",
    "                        break\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [inf] * (1 << n)\n",
    "        dp[0] = 0\n",
    "        group = n // k\n",
    "        values = {}\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if mask.bit_count() != group:\n",
    "                continue\n",
    "            mn = 20\n",
    "            mx = 0\n",
    "            cur = set()\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) > 0:\n",
    "                    if nums[i] in cur:\n",
    "                        break\n",
    "                    cur.add(nums[i])\n",
    "                    mn = min(mn, nums[i])\n",
    "                    mx = max(mx, nums[i])\n",
    "            if len(cur) == group:\n",
    "                values[mask] = mx - mn\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if dp[mask] == inf:\n",
    "                continue\n",
    "            seen = {}\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) == 0:\n",
    "                    seen[nums[i]] = i\n",
    "            if len(seen) < group:\n",
    "                continue\n",
    "            sub = 0\n",
    "            for v in seen:\n",
    "                sub |= 1 << seen[v]\n",
    "            nxt = sub\n",
    "            while nxt > 0:\n",
    "                if nxt in values:\n",
    "                    dp[mask | nxt] = min(dp[mask | nxt], dp[mask] + values[nxt])\n",
    "                nxt = (nxt - 1) & sub\n",
    "\n",
    "        return dp[-1] if dp[-1] < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        if max(Counter(nums).values()) > k:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        if m == 1:\n",
    "            return 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def chk(v):\n",
    "            if bin(v).count('1') == m:\n",
    "                t = set()\n",
    "                for i in range(n):\n",
    "                    if v & (1 << i):\n",
    "                        t.add(nums[i])\n",
    "                if len(t) == m:\n",
    "                    return max(t) - min(t)\n",
    "                else:\n",
    "                    return inf\n",
    "            t = set()\n",
    "            vt = -1\n",
    "            ret = inf\n",
    "            for i in range(n):\n",
    "                if v & (1 << i):\n",
    "                    vt = i\n",
    "                    break\n",
    "            t.add(nums[vt])\n",
    "            # print(v,bin(v), t)\n",
    "            def dfs(start, t, vv):\n",
    "                r = inf\n",
    "                for i in range(start, n):\n",
    "                    if nums[i] in t or (1 << i) & vv == 0:\n",
    "                        continue\n",
    "                    t.add(nums[i])\n",
    "                    vv ^= 1<<i\n",
    "                    \n",
    "                    if len(t) == m:\n",
    "                        # print(start, t, bin(vv), chk(vv)+max(t)-min(t))\n",
    "                        r = min(r, chk(vv)+max(t)-min(t))\n",
    "                    else:\n",
    "                        r = min(r, dfs(i+1,t,vv))\n",
    "                    vv ^= 1<<i\n",
    "                    t.remove(nums[i])\n",
    "                return r\n",
    "            return dfs(vt+1, t, v ^ (1 << vt))\n",
    "        return chk((1 << n) -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [inf] * (1 << n)\n",
    "        dp[0] = 0\n",
    "        group = n // k\n",
    "        values = {}\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if mask.bit_count() != group:\n",
    "                continue\n",
    "            mn = 20\n",
    "            mx = 0\n",
    "            cur = set()\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) > 0:\n",
    "                    if nums[i] in cur:\n",
    "                        break\n",
    "                    cur.add(nums[i])\n",
    "                    mn = min(mn, nums[i])\n",
    "                    mx = max(mx, nums[i])\n",
    "            if len(cur) == group:\n",
    "                values[mask] = mx - mn\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if dp[mask] == inf:\n",
    "                continue\n",
    "            seen = {}\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) == 0:\n",
    "                    seen[nums[i]] = i\n",
    "            if len(seen) < group:\n",
    "                continue\n",
    "            sub = 0\n",
    "            for v in seen:\n",
    "                sub |= 1 << seen[v]\n",
    "            nxt = sub\n",
    "            while nxt > 0:\n",
    "                if nxt in values:\n",
    "                    dp[mask | nxt] = min(dp[mask | nxt], dp[mask] + values[nxt])\n",
    "                nxt = (nxt - 1) & sub\n",
    "\n",
    "        return dp[-1] if dp[-1] < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        cnt=Counter(nums)\n",
    "        n=len(nums)\n",
    "        m=n//k\n",
    "        if max(cnt.values())>k:return -1\n",
    "        \n",
    "        dp=[inf]*(1<<n)\n",
    "        valid={}\n",
    "\n",
    "        for i in range(1,1<<n):\n",
    "            if i.bit_count()==m:\n",
    "                ma,mi=-inf,inf\n",
    "                bitmask=0\n",
    "                for j in range(n):\n",
    "                    if i>>j&1:\n",
    "                        if (1<<nums[j])&bitmask==0:\n",
    "                            # vis.add(nums[j])\n",
    "                            bitmask|=1<<nums[j]\n",
    "                            ma=max(ma,nums[j])\n",
    "                            mi=min(mi,nums[j])\n",
    "                        else:\n",
    "                            break\n",
    "                else:\n",
    "                    valid[i]=ma-mi\n",
    "\n",
    "        dp[0]=0\n",
    "        for i in range(1,1<<n):\n",
    "            s=i.bit_count()\n",
    "            if s%m!=0:continue\n",
    "            \n",
    "            for sub in valid:\n",
    "                if i&sub==sub:\n",
    "                    dp[i]=min(dp[i],dp[i^sub]+valid[sub])\n",
    "            # sub=i\n",
    "            # while sub:\n",
    "            #     if sub.bit_count()==m and sub in valid:\n",
    "            #         dp[i]=min(dp[i],dp[i^sub]+valid[sub])\n",
    "            #     sub=(sub-1)&i\n",
    "\n",
    "        return dp[-1] \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        # cnt=Counter(nums)\n",
    "        n=len(nums)\n",
    "        m=n//k\n",
    "        if m==1:return 0\n",
    "        # if max(cnt.values())>k:return -1\n",
    "        \n",
    "        dp=[inf]*(1<<n)\n",
    "        valid={}\n",
    "\n",
    "        for i in range(1,1<<n):\n",
    "            if i.bit_count()==m:\n",
    "                ma,mi=-inf,inf\n",
    "                bitmask=0\n",
    "                for j in range(n):\n",
    "                    if i>>j&1:\n",
    "                        if (1<<nums[j])&bitmask==0:\n",
    "                            # vis.add(nums[j])\n",
    "                            bitmask|=1<<nums[j]\n",
    "                            ma=max(ma,nums[j])\n",
    "                            mi=min(mi,nums[j])\n",
    "                        else:\n",
    "                            break\n",
    "                else:\n",
    "                    valid[i]=ma-mi\n",
    "\n",
    "        dp[0]=0\n",
    "        for i in range(1,1<<n):\n",
    "            s=i.bit_count()\n",
    "            if s%m!=0:continue\n",
    "            \n",
    "            sub=i\n",
    "            while sub:\n",
    "                if sub in valid:\n",
    "                    dp[i]=min(dp[i],dp[i^sub]+valid[sub])\n",
    "                sub=(sub-1)&i\n",
    "\n",
    "        return dp[-1] if dp[-1] !=inf else -1\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [inf] * (1 << len(nums))\n",
    "        dp[0] = 0\n",
    "        group = n // k\n",
    "        values = dict()\n",
    "\n",
    "        for m in range(1 << n):\n",
    "            if m.bit_count() != group:\n",
    "                continue\n",
    "            mn = 20\n",
    "            mx = 0\n",
    "            cur = set()\n",
    "            for i in range(n):\n",
    "                if m & (1 << i) > 0:\n",
    "                    if nums[i] in cur:\n",
    "                        break\n",
    "                    cur.add(nums[i])\n",
    "                    mn = min(mn, nums[i])\n",
    "                    mx = max(mx, nums[i])\n",
    "            else:\n",
    "                values[m] = mx - mn\n",
    "        \n",
    "        for m in range(1 << n):\n",
    "            if dp[m] == inf:\n",
    "                continue\n",
    "            seen = dict()\n",
    "            for i in range(n):\n",
    "                if m & (1 << i) == 0:\n",
    "                    seen[nums[i]] = i\n",
    "            if len(seen) < group:\n",
    "                continue\n",
    "            sub = 0\n",
    "            for v in seen:\n",
    "                sub |= 1 << seen[v]\n",
    "            nxt = sub\n",
    "            while nxt > 0:\n",
    "                if nxt in values:\n",
    "                    dp[m | nxt] = min(dp[m | nxt], dp[m] + values[nxt])\n",
    "                nxt = (nxt - 1) & sub\n",
    "            \n",
    "        return dp[-1] if dp[-1] < inf else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        size=n//k\n",
    "        if n==k:return 0\n",
    "        value=defaultdict(lambda:inf)\n",
    "        for i in range(1<<n):\n",
    "            mi,ma=inf,-inf\n",
    "            vis=set()\n",
    "            flag=0\n",
    "            if bin(i).count(\"1\")==size:\n",
    "                for j in range(n):\n",
    "                    if i>>j&1:\n",
    "                        if nums[j] in vis:\n",
    "                            flag=1\n",
    "                            break\n",
    "                        mi=min(mi,nums[j])\n",
    "                        ma=max(ma,nums[j])\n",
    "                        vis.add(nums[j])\n",
    "                \n",
    "                if not flag:\n",
    "                    value[i]=ma-mi\n",
    "        dp=[inf]*(1<<n)\n",
    "        dp[0]=0\n",
    "        for i in range(1,1<<n):\n",
    "            cnt=bin(i).count(\"1\")\n",
    "            sub=i\n",
    "            if cnt%size==0:\n",
    "                while sub:\n",
    "                    if sub in value:\n",
    "                        dp[i]=min(dp[i],dp[i-sub]+value[sub])\n",
    "                    sub=(sub-1)&i\n",
    "        return dp[-1] if dp[-1]!=inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        group = n // k\n",
    "        \n",
    "        dp = [inf] * (1 << n)\n",
    "        values = {}\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(2**n):\n",
    "            if i.bit_count() != group:\n",
    "                continue\n",
    "            mn = 20\n",
    "            mx = 0\n",
    "            cur = set()\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    if nums[j] in cur:\n",
    "                        break\n",
    "                    cur.add(nums[j])\n",
    "                    mn = min(mn, nums[j])\n",
    "                    mx = max(mx, nums[j])\n",
    "            if len(cur) == group:\n",
    "                values[i] = mx - mn\n",
    "        \n",
    "        for mask in range(1 << n):\n",
    "            if dp[mask] == inf:\n",
    "                continue\n",
    "            seen = {}\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) == 0:\n",
    "                    seen[nums[i]] = i\n",
    "            if len(seen) < group:\n",
    "                continue\n",
    "            sub = 0\n",
    "            for v in seen:\n",
    "                sub = sub | 1 << seen[v]\n",
    "            nxt = sub\n",
    "            while nxt > 0:\n",
    "                if nxt in values:\n",
    "                    dp[mask | nxt] = min(dp[mask | nxt], dp[mask] + values[nxt])\n",
    "                nxt = (nxt - 1) & sub\n",
    "            \n",
    "        return dp[-1] if dp[-1] < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [inf] * (1 << n)\n",
    "        dp[0] = 0\n",
    "        group = n // k\n",
    "        values = {}\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if mask.bit_count() != group:\n",
    "                continue\n",
    "            mn = 20\n",
    "            mx = 0\n",
    "            cur = set()\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) > 0:\n",
    "                    if nums[i] in cur:\n",
    "                        break\n",
    "                    cur.add(nums[i])\n",
    "                    mn = min(mn, nums[i])\n",
    "                    mx = max(mx, nums[i])\n",
    "            if len(cur) == group:\n",
    "                values[mask] = mx - mn\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if dp[mask] == inf:\n",
    "                continue\n",
    "            seen = {}\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) == 0:\n",
    "                    seen[nums[i]] = i\n",
    "            if len(seen) < group:\n",
    "                continue\n",
    "            sub = 0\n",
    "            for v in seen:\n",
    "                sub |= 1 << seen[v]\n",
    "            nxt = sub\n",
    "            while nxt > 0:\n",
    "                if nxt in values:\n",
    "                    dp[mask | nxt] = min(dp[mask | nxt], dp[mask] + values[nxt])\n",
    "                nxt = (nxt - 1) & sub\n",
    "\n",
    "        return dp[-1] if dp[-1] < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [inf] * (1 << n)\n",
    "        dp[0] = 0\n",
    "        group = n // k\n",
    "        values = {}\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if mask.bit_count() != group:\n",
    "                continue\n",
    "            mn = 20\n",
    "            mx = 0\n",
    "            cur = set()\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) > 0:\n",
    "                    if nums[i] in cur:\n",
    "                        break\n",
    "                    cur.add(nums[i])\n",
    "                    mn = min(mn, nums[i])\n",
    "                    mx = max(mx, nums[i])\n",
    "            if len(cur) == group:\n",
    "                values[mask] = mx - mn\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if dp[mask] == inf:\n",
    "                continue\n",
    "            seen = {}\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) == 0:\n",
    "                    seen[nums[i]] = i\n",
    "            if len(seen) < group:\n",
    "                continue\n",
    "            sub = 0\n",
    "            for v in seen:\n",
    "                sub |= 1 << seen[v]\n",
    "            nxt = sub\n",
    "            while nxt > 0:\n",
    "                if nxt in values:\n",
    "                    dp[mask | nxt] = min(dp[mask | nxt], dp[mask] + values[nxt])\n",
    "                nxt = (nxt - 1) & sub\n",
    "\n",
    "        return dp[-1] if dp[-1] < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        m=n//k\n",
    "        if m==1:return 0\n",
    "        \n",
    "        dp=[inf]*(1<<n)\n",
    "        valid={}\n",
    "\n",
    "        for i in range(1,1<<n):\n",
    "            if i.bit_count()==m:\n",
    "                ma,mi=-inf,inf\n",
    "                bitmask=0\n",
    "                for j in range(n):\n",
    "                    if i>>j&1:\n",
    "                        if (1<<nums[j])&bitmask==0:\n",
    "                            # vis.add(nums[j])\n",
    "                            bitmask|=1<<nums[j]\n",
    "                            ma=max(ma,nums[j])\n",
    "                            mi=min(mi,nums[j])\n",
    "                        else:\n",
    "                            break\n",
    "                else:\n",
    "                    valid[i]=ma-mi\n",
    "\n",
    "        dp[0]=0\n",
    "        for i in range(1,1<<n):\n",
    "            s=i.bit_count()\n",
    "            if s%m!=0:continue\n",
    "            \n",
    "            sub=i\n",
    "            while sub:\n",
    "                if sub in valid:\n",
    "                    dp[i]=min(dp[i],dp[i^sub]+valid[sub])\n",
    "                sub=(sub-1)&i\n",
    "\n",
    "        return dp[-1] if dp[-1] !=inf else -1\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [-1] * (1 << n)\n",
    "        for i in range(1, 1 << n):\n",
    "            if i.bit_count() != m:\n",
    "                continue\n",
    "            s = set()\n",
    "            mi, mx = 20, 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if i >> j & 1:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                    mi = min(mi, x)\n",
    "                    mx = max(mx, x)\n",
    "            if len(s) == m:\n",
    "                g[i] = mx - mi\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << n):\n",
    "            if f[i] == inf:\n",
    "                continue\n",
    "            s = set()\n",
    "            mask = 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if (i >> j & 1) == 0 and x not in s:\n",
    "                    s.add(x)\n",
    "                    mask |= 1 << j\n",
    "            if len(s) < m:\n",
    "                continue\n",
    "            j = mask\n",
    "            while j:\n",
    "                if g[j] != -1:\n",
    "                    f[i | j] = min(f[i | j], f[i] + g[j])\n",
    "                j = (j - 1) & mask\n",
    "        return f[-1] if f[-1] != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [-1] * (1 << n)\n",
    "        for i in range(1, 1 << n):\n",
    "            if i.bit_count() != m:\n",
    "                continue\n",
    "            s = set()\n",
    "            mi, mx = 20, 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if i >> j & 1:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                    mi = min(mi, x)\n",
    "                    mx = max(mx, x)\n",
    "            if len(s) == m:\n",
    "                g[i] = mx - mi\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << n):\n",
    "            if f[i] == inf:\n",
    "                continue\n",
    "            s = set()\n",
    "            mask = 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if (i >> j & 1) == 0 and x not in s:\n",
    "                    s.add(x)\n",
    "                    mask |= 1 << j\n",
    "            if len(s) < m:\n",
    "                continue\n",
    "            j = mask\n",
    "            while j:\n",
    "                if g[j] != -1:\n",
    "                    f[i | j] = min(f[i | j], f[i] + g[j])\n",
    "                j = (j - 1) & mask\n",
    "        return f[-1] if f[-1] != inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [-1] * (1 << n)\n",
    "        for i in range(1, 1 << n):\n",
    "            if i.bit_count() != m:\n",
    "                continue\n",
    "            s = set()\n",
    "            mi, mx = 20, 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if i >> j & 1:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                    mi = min(mi, x)\n",
    "                    mx = max(mx, x)\n",
    "            if len(s) == m:\n",
    "                g[i] = mx - mi\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << n):\n",
    "            if f[i] == inf:\n",
    "                continue\n",
    "            s = set()\n",
    "            mask = 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if (i >> j & 1) == 0 and x not in s:\n",
    "                    s.add(x)\n",
    "                    mask |= 1 << j\n",
    "            if len(s) < m:\n",
    "                continue\n",
    "            j = mask\n",
    "            while j:\n",
    "                if g[j] != -1:\n",
    "                    f[i | j] = min(f[i | j], f[i] + g[j])\n",
    "                j = (j - 1) & mask\n",
    "        return f[-1] if f[-1] != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        # 1 1 2 2 3 3 6 8\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [-1] * (1 << n) \n",
    "        for i in range(1, 1 << n):\n",
    "            if i.bit_count() != m:\n",
    "                continue\n",
    "            s = set()\n",
    "            mx, mn = 0, 20\n",
    "            for j, x in enumerate(nums):\n",
    "                if i >> j & 1:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                    mx, mn = max(mx, x), min(mn, x)\n",
    "            if len(s) == m:\n",
    "                g[i] = mx - mn\n",
    "        print(f'{g}')\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << n):\n",
    "            if f[i] == inf: continue\n",
    "            if i.bit_count() % m:\n",
    "                continue\n",
    "            mask, s = 0, set()\n",
    "            for j, x in enumerate(nums):\n",
    "                if (i >> j & 1) == 0 and x not in s:\n",
    "                    mask |=  1 << j\n",
    "                    s.add(x)\n",
    "            if len(s) < m:\n",
    "                continue\n",
    "            j = mask\n",
    "            while j:\n",
    "                if g[j] != -1:\n",
    "                    f[i|j] = min(f[i|j], f[i] + g[j])\n",
    "                j = (j - 1) & mask\n",
    "        return -1 if f[-1] == inf else f[-1]\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [-1] * (1 << n)\n",
    "        for i in range(1, 1 << n):\n",
    "            if i.bit_count() != m:\n",
    "                continue\n",
    "            s = set()\n",
    "            mi, mx = 20, 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if i >> j & 1:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                    mi = min(mi, x)\n",
    "                    mx = max(mx, x)\n",
    "            if len(s) == m:\n",
    "                g[i] = mx - mi\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << n):\n",
    "            if f[i] == inf:\n",
    "                continue\n",
    "            s = set()\n",
    "            mask = 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if (i >> j & 1) == 0 and x not in s:\n",
    "                    s.add(x)\n",
    "                    mask |= 1 << j\n",
    "            if len(s) < m:\n",
    "                continue\n",
    "            j = mask\n",
    "            while j:\n",
    "                if g[j] != -1:\n",
    "                    f[i | j] = min(f[i | j], f[i] + g[j])\n",
    "                j = (j - 1) & mask\n",
    "        return f[-1] if f[-1] != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\"\"\" \n",
    "状压DP + 预处理\n",
    "先预处理出每个合法子集的不兼容值：枚举msk ∈ [1, 1 << n - 1]的集合，其中二进制位为1的下标i表示nums[i]被选中，先检查mask中1的个数是否为size = n / k，然后再检查选中的元素中是否有重复的，可以用二进制来优化检查。时间为O(n * 2^n)，需要枚举O(2^n)个二进制数，每次枚举需要O(n)时间来检查、计算；空间为O(2^n)，共O(2^n)个状态的值需要存储。\n",
    "然后枚举已选择元素集合mask，表示二进制中为1的位已经被选出来构成给各个有效的子集，从mask = 0开始枚举，dp[mask]表示选中的元素为mask时的最小不兼容性和，那么dp[0]=0，然后再枚举剩余未选中元素集合rem的每个子集sub，如果sub合法，也即也可以构成一个子集：values[sub] > 0，那么有dp[mask | sub] = min(dp[mask] + values[sub])，枚举rem的非空子集sub可以使用sub = (sub - 1) & rem的方式。最后结果返回dp[1 << n - 1]即可。时间为O(3^n)，每个元素只有三种状态：（已选，将选，未选），所以转移方程最多被执行O(3^n)次，由于预处理时间O(n * 2^n)小于O(3^n)，所以总时间为O(3^n)。dp数组、预处理数组的空间均为O(2^n)。\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        INF = 10 ** 9\n",
    "\n",
    "        n = len(nums)\n",
    "        size = n / k\n",
    "        if size == 1:\n",
    "            return 0\n",
    "\n",
    "        # 检查是否有元素个数超过nums，如果有则不存在合法的划分方案\n",
    "        if max(Counter(nums).values()) > k:\n",
    "            return -1\n",
    "\n",
    "        # 预处理每个有效子集的不兼容性值\n",
    "        values = [0] * (1 << n)\n",
    "        for mask in range(1, 1 << n):\n",
    "            if mask.bit_count() != size:\n",
    "                continue\n",
    "            suc = True\n",
    "            val = 0\n",
    "            mx, mn = -INF, INF\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1 == 0:\n",
    "                    continue\n",
    "                if (val >> nums[i]) & 1 > 0:\n",
    "                    suc = False\n",
    "                    break\n",
    "                val |= 1 << nums[i]\n",
    "                mx = max(mx, nums[i])\n",
    "                mn = min(mn, nums[i])\n",
    "            if suc:\n",
    "                values[mask] = mx - mn\n",
    "\n",
    "        # 枚举每个已选元素集合mask，从未选元素集合rem中选出非空子集sub，如果sub是一个合法的子集，则更新dp[mask | sub] = min(dp[mask] + values[sub])，sub的枚举可以使用：sub = (sub - 1) & rem完成\n",
    "        dp = [INF] * (1 << n)\n",
    "        dp[0] = 0\n",
    "        for mask in range(1 << n):\n",
    "            if dp[mask] == INF:  # mask不是一个合法的已选元素集合，也即mask中的元素无法划分为数个有效的子集\n",
    "                continue\n",
    "            rem = ((1 << n) - 1) ^ mask\n",
    "            sub = rem\n",
    "            while sub:\n",
    "                if values[sub] > 0:\n",
    "                    dp[mask | sub] = min(\n",
    "                        dp[mask | sub], dp[mask] + values[sub])\n",
    "                sub = (sub - 1) & rem\n",
    "\n",
    "        return dp[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [-1] * (1 << n)\n",
    "        for i in range(1, 1 << n):\n",
    "            if i.bit_count() != m:\n",
    "                continue\n",
    "            s = set()\n",
    "            mi, mx = 20, 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if i >> j & 1:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                    mi = min(mi, x)\n",
    "                    mx = max(mx, x)\n",
    "            if len(s) == m:\n",
    "                g[i] = mx - mi\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << n):\n",
    "            if f[i] == inf:\n",
    "                continue\n",
    "            s = set()\n",
    "            mask = 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if (i >> j & 1) == 0 and x not in s:\n",
    "                    s.add(x)\n",
    "                    mask |= 1 << j\n",
    "            if len(s) < m:\n",
    "                continue\n",
    "            j = mask\n",
    "            while j:\n",
    "                if g[j] != -1:\n",
    "                    f[i | j] = min(f[i | j], f[i] + g[j])\n",
    "                j = (j - 1) & mask\n",
    "        return f[-1] if f[-1] != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        count = Counter(nums)\n",
    "        if max(count.values())>k:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        basket = [0 for _ in range(k)]\n",
    "        tar_len = n // k\n",
    "\n",
    "        # 预处理\n",
    "        g = [-1 for _ in range(1<<n)]\n",
    "        res = 0\n",
    "        for state in range(1,1<<n):\n",
    "            # print(bin(basket[u]))\n",
    "            s = set()\n",
    "            if bin(state).count('1') == tar_len:\n",
    "                mx = 0\n",
    "                mn = 20\n",
    "                for i,v in enumerate(nums):\n",
    "                    if (1 << i) & state:\n",
    "                        if v in s:\n",
    "                            break\n",
    "                        s.add(v)\n",
    "                        mx = max(mx, v)\n",
    "                        mn = min(mn, v)\n",
    "                if len(s) == tar_len:\n",
    "                    g[state] = mx - mn\n",
    "\n",
    "        f = [float('inf')] * (1<<n)\n",
    "        f[0] = 0\n",
    "        for mask in range(1<<n):\n",
    "            if f[mask] == float('inf'):\n",
    "                continue\n",
    "\n",
    "            sub = 0 # 不重复的补集\n",
    "            s = set()\n",
    "            for i,v in enumerate(nums):\n",
    "                if not (1<<i) & mask and v not in s:\n",
    "                    s.add(v)\n",
    "                    sub |= (1<<i)\n",
    "            if len(s) < tar_len:\n",
    "                continue\n",
    "            # 遍历补集的子集f[mask|sub] = f[mask] + f[sub]\n",
    "            nxt = sub\n",
    "            while nxt:\n",
    "                if g[nxt]!=-1:\n",
    "                    f[mask | nxt] = min(f[mask | nxt], f[mask] + g[nxt])\n",
    "                nxt = (nxt-1) & sub\n",
    "        return f[(1<<n)-1] if f[(1<<n)-1]!=float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [-1] * (1 << n)\n",
    "        for i in range(1, 1 << n):\n",
    "            if i.bit_count() != m:\n",
    "                continue\n",
    "            s = set()\n",
    "            mi, mx = 20, 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if i >> j & 1:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                    mi = min(mi, x)\n",
    "                    mx = max(mx, x)\n",
    "            if len(s) == m:\n",
    "                g[i] = mx - mi\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << n):\n",
    "            if f[i] == inf:\n",
    "                continue\n",
    "            s = set()\n",
    "            mask = 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if (i >> j & 1) == 0 and x not in s:\n",
    "                    s.add(x)\n",
    "                    mask |= 1 << j\n",
    "            if len(s) < m:\n",
    "                continue\n",
    "            j = mask\n",
    "            while j:\n",
    "                if g[j] != -1:\n",
    "                    f[i | j] = min(f[i | j], f[i] + g[j])\n",
    "                j = (j - 1) & mask\n",
    "        return f[-1] if f[-1] != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        # 1 1 2 2 3 3 6 8\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [-1] * (1 << n) \n",
    "        for i in range(1, 1 << n):\n",
    "            if i.bit_count() != m:\n",
    "                continue\n",
    "            s = set()\n",
    "            mx, mn = 0, 20\n",
    "            for j, x in enumerate(nums):\n",
    "                if i >> j & 1:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                    mx, mn = max(mx, x), min(mn, x)\n",
    "            if len(s) == m:\n",
    "                g[i] = mx - mn\n",
    "        print(f'{g}')\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << n):\n",
    "            if f[i] == inf: continue\n",
    "            # if i.bit_count() % m:\n",
    "                # continue\n",
    "            mask, s = 0, set()\n",
    "            for j, x in enumerate(nums):\n",
    "                if (i >> j & 1) == 0 and x not in s:\n",
    "                    mask |=  1 << j\n",
    "                    s.add(x)\n",
    "            if len(s) < m:\n",
    "                continue\n",
    "            j = mask\n",
    "            while j:\n",
    "                if g[j] != -1:\n",
    "                    f[i|j] = min(f[i|j], f[i] + g[j])\n",
    "                j = (j - 1) & mask\n",
    "        return -1 if f[-1] == inf else f[-1]\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        # 1 1 2 2 3 3 6 8\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [-1] * (1 << n) \n",
    "        for i in range(1, 1 << n):\n",
    "            if i.bit_count() != m:\n",
    "                continue\n",
    "            s = set()\n",
    "            mx, mn = 0, 20\n",
    "            for j, x in enumerate(nums):\n",
    "                if i >> j & 1:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                    mx, mn = max(mx, x), min(mn, x)\n",
    "            if len(s) == m:\n",
    "                g[i] = mx - mn\n",
    "        print(f'{g}')\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << n):\n",
    "            # if f[i] == inf: continue\n",
    "            if i.bit_count() % m:\n",
    "                continue\n",
    "            mask, s = 0, set()\n",
    "            for j, x in enumerate(nums):\n",
    "                if (i >> j & 1) == 0 and x not in s:\n",
    "                    mask |=  1 << j\n",
    "                    s.add(x)\n",
    "            if len(s) < m:\n",
    "                continue\n",
    "            j = mask\n",
    "            while j:\n",
    "                if g[j] != -1:\n",
    "                    f[i|j] = min(f[i|j], f[i] + g[j])\n",
    "                j = (j - 1) & mask\n",
    "        return -1 if f[-1] == inf else f[-1]\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums)\n",
    "        if max(cnt.values()) > k:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "\n",
    "        m = n//k\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if not state:\n",
    "                return 0\n",
    "            res = inf\n",
    "            lst =[]\n",
    "            pre = set()\n",
    "            for i in range(n):\n",
    "                if state & (1 << i) and nums[i] not in pre:\n",
    "                    lst.append(i)\n",
    "                    pre.add(nums[i])\n",
    "            for item in combinations(lst, m):\n",
    "\n",
    "                cur = max(nums[i] for i in item) - min(nums[i] for i in item)\n",
    "                if cur > res:\n",
    "                    break\n",
    "                nex = state ^ sum(1<<i for i in item)\n",
    "                cur += dfs(nex)\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "                \n",
    "            return res\n",
    "\n",
    "        return dfs((1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 特殊判断，如果元素数量等于组数\n",
    "        if n == k:\n",
    "            return 0\n",
    "        \n",
    "        value = dict()\n",
    "        for sub in range(1 << n):\n",
    "            # 判断 sub 是否有 n/k 个 1\n",
    "            if bin(sub).count(\"1\") == n // k:\n",
    "                # 使用哈希表进行计数\n",
    "                freq = set()\n",
    "                flag = True\n",
    "                for j in range(n):\n",
    "                    if sub & (1 << j):\n",
    "                        # 任意一个数不能出现超过 1 次\n",
    "                        if nums[j] in freq:\n",
    "                            flag = False\n",
    "                            break\n",
    "                        freq.add(nums[j])\n",
    "                \n",
    "                # 如果满足要求，那么计算 sub 的不兼容性\n",
    "                if flag:\n",
    "                    value[sub] = max(freq) - min(freq)\n",
    "        \n",
    "        f = dict()\n",
    "        f[0] = 0\n",
    "        for mask in range(1 << n):\n",
    "            # 判断 mask 是否有 n/k 倍数个 1\n",
    "            if bin(mask).count(\"1\") % (n // k) == 0:\n",
    "                # 枚举子集\n",
    "                sub = mask\n",
    "                while sub > 0:\n",
    "                    if sub in value and mask ^ sub in f:\n",
    "                        if mask not in f:\n",
    "                            f[mask] = f[mask ^ sub] + value[sub]\n",
    "                        else:\n",
    "                            f[mask] = min(f[mask], f[mask ^ sub] + value[sub])\n",
    "                    sub = (sub - 1) & mask\n",
    "            \n",
    "        return -1 if (1 << n) - 1 not in f else f[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums)\n",
    "        if max(cnt.values()) > k:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "\n",
    "        m = n//k\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if not state:\n",
    "                return 0\n",
    "            res = inf\n",
    "            lst =[]\n",
    "            pre = set()\n",
    "            for i in range(n):\n",
    "                if state & (1 << i) and nums[i] not in pre:\n",
    "                    lst.append(i)\n",
    "                    pre.add(nums[i])\n",
    "            for item in combinations(lst, m):\n",
    "\n",
    "                cur = max(nums[i] for i in item) - min(nums[i] for i in item)\n",
    "                nex = state ^ sum(1<<i for i in item)\n",
    "                cur += dfs(nex)\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "                \n",
    "            return res\n",
    "\n",
    "        return dfs((1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums)\n",
    "        mx = max(cnt.values())\n",
    "        if mx > k: return -1\n",
    "        \n",
    "        m = n // k\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            if state == ((1 << n) - 1):\n",
    "                return 0\n",
    "            res = inf\n",
    "            left = dict() # 去重\n",
    "            for i in range(n):\n",
    "                if (state >> i & 1) == 0:\n",
    "                    left[nums[i]] = i # 每个数字，只保留一个下标，避免后续选到重复数字\n",
    "            for com in itertools.combinations(left.keys(), m):\n",
    "                nstate = state\n",
    "                for j in com:\n",
    "                    nstate |= (1 << left[j])\n",
    "                res = min(res, max(com) - min(com) + dfs(nstate))\n",
    "            return res\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums)\n",
    "        mx = max(cnt.values())\n",
    "        if mx > k: return -1\n",
    "        \n",
    "        m = n // k\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            if state == ((1 << n) - 1):\n",
    "                return 0\n",
    "            res = inf\n",
    "            left = dict()\n",
    "            for i in range(n):\n",
    "                if (state >> i & 1) == 0:\n",
    "                    left[nums[i]] = i\n",
    "            for com in itertools.combinations(left.keys(), m):\n",
    "                nstate = state\n",
    "                for j in com:\n",
    "                    nstate |= (1 << left[j])\n",
    "                res = min(res, max(com) - min(com) + dfs(nstate))\n",
    "            return res\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        value = dict()\n",
    "        for sub in range(1 << n):\n",
    "            # 判断 sub 是否有 n/k 个 1\n",
    "            if bin(sub).count(\"1\") == n // k:\n",
    "                # 使用哈希表进行计数\n",
    "                freq = set()\n",
    "                flag = True\n",
    "                for j in range(n):\n",
    "                    if sub & (1 << j):\n",
    "                        # 任意一个数不能出现超过 1 次\n",
    "                        if nums[j] in freq:\n",
    "                            flag = False\n",
    "                            break\n",
    "                        freq.add(nums[j])\n",
    "                \n",
    "                # 如果满足要求，那么计算 sub 的不兼容性\n",
    "                if flag:\n",
    "                    value[sub] = max(freq) - min(freq)\n",
    "        \n",
    "        f = dict()\n",
    "        f[0] = 0\n",
    "        for mask in range(1 << n):\n",
    "            # 判断 mask 是否有 n/k 倍数个 1\n",
    "            if bin(mask).count(\"1\") % (n // k) == 0:\n",
    "                # 如果子集个数小于 value 中满足要求的子集个数，我们才枚举子集\n",
    "                if 2**bin(mask).count(\"1\") < len(value):\n",
    "                    sub = mask\n",
    "                    while sub > 0:\n",
    "                        if sub in value and mask ^ sub in f:\n",
    "                            if mask not in f:\n",
    "                                f[mask] = f[mask ^ sub] + value[sub]\n",
    "                            else:\n",
    "                                f[mask] = min(f[mask], f[mask ^ sub] + value[sub])\n",
    "                        sub = (sub - 1) & mask\n",
    "                else:\n",
    "                    for sub, v in value.items():\n",
    "                        if (mask & sub) == sub and mask ^ sub in f:\n",
    "                            if mask not in f:\n",
    "                                f[mask] = f[mask ^ sub] + v\n",
    "                            else:\n",
    "                                f[mask] = min(f[mask], f[mask ^ sub] + v)\n",
    "            \n",
    "        return -1 if (1 << n) - 1 not in f else f[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        for i in set(nums):\n",
    "            if nums.count(i)>k:\n",
    "                return -1\n",
    "        n = len(nums)\n",
    "        size = n // k\n",
    "        nums.sort()  # 排序，便于判断重复\n",
    "\n",
    "        @cache\n",
    "        def dfs(left: int, pre: int) -> int:\n",
    "            if left == 0: return 0\n",
    "            if left.bit_count() % size == 0:  # 创建一个新的组\n",
    "                lb = left & -left  # 选择 lowbit 作为第一个数\n",
    "                return dfs(left ^ lb, lb.bit_length() - 1)\n",
    "            res = inf\n",
    "            last = nums[pre]\n",
    "            for i in range(pre + 1, n):  # 枚举这个组的下一个数\n",
    "                if left >> i & 1 and nums[i] != last:  # 组内不能有重复数字，且 a 中重复数字只需枚举一次\n",
    "                    last = nums[i]\n",
    "                    res = min(res, last - nums[pre] + dfs(left ^ (1 << i), i))\n",
    "            return res\n",
    "\n",
    "        return dfs((1 << n) - 2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        if any(c > k for c in Counter(nums).values()):  # 鸽巢原理\n",
    "            return -1\n",
    "\n",
    "        n = len(nums)\n",
    "        size = n // k\n",
    "        nums.sort()  # 排序，便于判断重复\n",
    "\n",
    "        @cache\n",
    "        def dfs(left: int, pre: int) -> int:\n",
    "            if left == 0: return 0\n",
    "            if left.bit_count() % size == 0:  # 创建一个新的组\n",
    "                lb = left & -left  # 选择 lowbit 作为第一个数\n",
    "                return dfs(left ^ lb, lb.bit_length() - 1)\n",
    "            res = inf\n",
    "            last = nums[pre]\n",
    "            for i in range(pre + 1, n):  # 枚举这个组的下一个数\n",
    "                if left >> i & 1 and nums[i] != last:  # 组内不能有重复数字，且 nums 中重复数字只需枚举一次\n",
    "                    last = nums[i]\n",
    "                    res = min(res, last - nums[pre] + dfs(left ^ (1 << i), i))\n",
    "            return res\n",
    "\n",
    "        return dfs((1 << n) - 2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, a: List[int], k: int) -> int:\n",
    "        if any(c > k for c in Counter(a).values()):  # 鸽巢原理\n",
    "            return -1\n",
    "\n",
    "        n = len(a)\n",
    "        size = n // k\n",
    "        a.sort()  # 排序，便于判断重复\n",
    "\n",
    "        @cache\n",
    "        def dfs(left: int, pre: int) -> int:\n",
    "            if left == 0: return 0\n",
    "            if left.bit_count() % size == 0:  # 创建一个新的组\n",
    "                lb = left & -left  # 选择 lowbit 作为第一个数\n",
    "                return dfs(left ^ lb, lb.bit_length() - 1)\n",
    "            res = inf\n",
    "            last = a[pre]\n",
    "            for i in range(pre + 1, n):  # 枚举这个组的下一个数\n",
    "                if left >> i & 1 and a[i] != last:  # 组内不能有重复数字，且 a 中重复数字只需枚举一次\n",
    "                    last = a[i]\n",
    "                    res = min(res, last - a[pre] + dfs(left ^ (1 << i), i))\n",
    "            return res\n",
    "\n",
    "        return dfs((1 << n) - 2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, a: List[int], k: int) -> int:\n",
    "        if any(c > k for c in Counter(a).values()):  # 鸽巢原理\n",
    "            return -1\n",
    "\n",
    "        n = len(a)\n",
    "        size = n // k\n",
    "        a.sort()  # 排序，便于判断重复\n",
    "\n",
    "        @cache\n",
    "        def dfs(left: int, pre: int) -> int:\n",
    "            if left == 0: return 0\n",
    "            if left.bit_count() % size == 0:  # 创建一个新的组\n",
    "                lb = left & -left  # 选择 lowbit 作为第一个数\n",
    "                return dfs(left ^ lb, lb.bit_length() - 1)\n",
    "            res = inf\n",
    "            last = a[pre]\n",
    "            for i in range(pre + 1, n):  # 枚举这个组的下一个数\n",
    "                if left >> i & 1 and a[i] != last:  # 组内不能有重复数字，且 a 中重复数字只需枚举一次\n",
    "                    last = a[i]\n",
    "                    res = min(res, last - a[pre] + dfs(left ^ (1 << i), i))\n",
    "            return res\n",
    "\n",
    "        return dfs((1 << n) - 2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        self.kn = len(nums) // k\n",
    "        nums = sorted(nums)\n",
    "        @functools.lru_cache(None)\n",
    "        \n",
    "\n",
    "        def solve(state = 0, lastp = -1) :\n",
    "            p0s = [i for i in range(len(nums)) if not (1<<i) & state]\n",
    "            if len(p0s) == 0 :\n",
    "                return 0\n",
    "\n",
    "            if lastp >= len(nums) :\n",
    "                return 1e99\n",
    "\n",
    "            if len(p0s) % self.kn == 0 :\n",
    "                return solve(state|(1<<p0s[0]), p0s[0])\n",
    "            \n",
    "            # 一个有意思的剪枝\n",
    "            if len(p0s) % self.kn > 1 :\n",
    "                p0s = p0s[:- (len(p0s) % self.kn -  1)]\n",
    "            \n",
    "            to_ret = 1e99\n",
    "            for t in p0s :\n",
    "                if nums[t] <= nums[lastp] :\n",
    "                    continue\n",
    "\n",
    "                to_ret = min(to_ret, nums[t] - nums[lastp] + solve(state|(1<<t), t))\n",
    "            return to_ret\n",
    "            \n",
    "        to_ret = solve()\n",
    "        if to_ret > 1e66 :\n",
    "            return -1\n",
    "        return to_ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums, k):\n",
    "        n = len(nums)\n",
    "        if k == n: return 0\n",
    "        dp = [[float(\"inf\")] * n for _ in range(1<<n)] \n",
    "        nums.sort()\n",
    "        for i in range(n): dp[1<<i][i] = 0\n",
    "\n",
    "        for mask in range(1<<n):\n",
    "            n_z_bits = [j for j in range(n) if mask&(1<<j)]\n",
    "            if len(n_z_bits)%(n//k) == 1:\n",
    "                for j, l in permutations(n_z_bits, 2):\n",
    "                    dp[mask][l] = min(dp[mask][l], dp[mask^(1<<l)][j])\n",
    "            else:\n",
    "                for j, l in combinations(n_z_bits, 2):\n",
    "                    if nums[j] != nums[l]:\n",
    "                        dp[mask][j] = min(dp[mask][j], dp[mask^(1<<j)][l] + nums[l] - nums[j])\n",
    "                        \n",
    "        return min(dp[-1]) if min(dp[-1]) != float(\"inf\") else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums, k):\n",
    "        n = len(nums)\n",
    "        if k == n: return 0\n",
    "        dp = [[float(\"inf\")] * n for _ in range(1<<n)] \n",
    "        nums.sort()\n",
    "        for i in range(n): dp[1<<i][i] = 0\n",
    "\n",
    "        for mask in range(1<<n):\n",
    "            n_z_bits = [j for j in range(n) if mask&(1<<j)]\n",
    "            if len(n_z_bits)%(n//k) == 1:\n",
    "                for j, l in permutations(n_z_bits, 2):\n",
    "                    dp[mask][l] = min(dp[mask][l], dp[mask^(1<<l)][j])\n",
    "            else:\n",
    "                for j, l in combinations(n_z_bits, 2):\n",
    "                    if nums[j] != nums[l]:\n",
    "                        dp[mask][j] = min(dp[mask][j], dp[mask^(1<<j)][l] + nums[l] - nums[j])\n",
    "                        \n",
    "        return min(dp[-1]) if min(dp[-1]) != float(\"inf\") else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = n // k\n",
    "        g = [-1] * (1 << n)\n",
    "        for i in range(1, 1 << n):\n",
    "            if i.bit_count() != m:\n",
    "                continue\n",
    "            s = set()\n",
    "            mi, mx = 20, 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if i >> j & 1:\n",
    "                    if x in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                    mi = min(mi, x)\n",
    "                    mx = max(mx, x)\n",
    "            if len(s) == m:\n",
    "                g[i] = mx - mi\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1 << n):\n",
    "            if f[i] == inf:\n",
    "                continue\n",
    "            s = set()\n",
    "            mask = 0\n",
    "            for j, x in enumerate(nums):\n",
    "                if (i >> j & 1) == 0 and x not in s:\n",
    "                    s.add(x)\n",
    "                    mask |= 1 << j\n",
    "            if len(s) < m:\n",
    "                continue\n",
    "            j = mask\n",
    "            while j:\n",
    "                if g[j] != -1:\n",
    "                    f[i | j] = min(f[i | j], f[i] + g[j])\n",
    "                j = (j - 1) & mask\n",
    "        return f[-1] if f[-1] != inf else -1\n",
    "\n",
    "from typing import *\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [inf] * (1 << n)\n",
    "        dp[0] = 0\n",
    "        group = n // k\n",
    "        values = {}\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if mask.bit_count() != group:\n",
    "                continue\n",
    "            mn = 20\n",
    "            mx = 0\n",
    "            cur = set()\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) > 0:\n",
    "                    if nums[i] in cur:\n",
    "                        break\n",
    "                    cur.add(nums[i])\n",
    "                    mn = min(mn, nums[i])\n",
    "                    mx = max(mx, nums[i])\n",
    "            if len(cur) == group:\n",
    "                values[mask] = mx - mn\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if dp[mask] == inf:\n",
    "                continue\n",
    "            seen = {}\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) == 0:\n",
    "                    seen[nums[i]] = i\n",
    "            if len(seen) < group:\n",
    "                continue\n",
    "            sub = 0\n",
    "            for v in seen:\n",
    "                sub |= 1 << seen[v]\n",
    "            nxt = sub\n",
    "            while nxt > 0:\n",
    "                if nxt in values:\n",
    "                    dp[mask | nxt] = min(dp[mask | nxt], dp[mask] + values[nxt])\n",
    "                nxt = (nxt - 1) & sub\n",
    "\n",
    "        return dp[-1] if dp[-1] < inf else -1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, a: List[int], k: int) -> int:\n",
    "        if any(c > k for c in Counter(a).values()):  # 鸽巢原理\n",
    "            return -1\n",
    "\n",
    "        n = len(a)\n",
    "        size = n // k\n",
    "        a.sort()  # 排序，便于判断重复\n",
    "\n",
    "        @cache\n",
    "        def dfs(left: int, pre: int) -> int:\n",
    "            if left == 0: return 0\n",
    "            if left.bit_count() % size == 0:  # 创建一个新的组\n",
    "                lb = left & -left  # 选择 lowbit 作为第一个数\n",
    "                return dfs(left ^ lb, lb.bit_length() - 1)\n",
    "            res = inf\n",
    "            last = a[pre]\n",
    "            for i in range(pre + 1, n):  # 枚举这个组的下一个数\n",
    "                if left >> i & 1 and a[i] != last:  # 组内不能有重复数字，且 a 中重复数字只需枚举一次\n",
    "                    last = a[i]\n",
    "                    res = min(res, last - a[pre] + dfs(left ^ (1 << i), i))\n",
    "            return res\n",
    "\n",
    "        return dfs((1 << n) - 2, 0)\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums, k):\n",
    "        n = len(nums)\n",
    "        if k == n: return 0\n",
    "        dp = [[float(\"inf\")] * n for _ in range(1<<n)] \n",
    "        nums.sort()\n",
    "        for i in range(n): dp[1<<i][i] = 0\n",
    "\n",
    "        for mask in range(1<<n):\n",
    "            n_z_bits = [j for j in range(n) if mask&(1<<j)]\n",
    "            if len(n_z_bits)%(n//k) == 1:\n",
    "                for j, l in permutations(n_z_bits, 2):\n",
    "                    dp[mask][l] = min(dp[mask][l], dp[mask^(1<<l)][j])\n",
    "            else:\n",
    "                for j, l in combinations(n_z_bits, 2):\n",
    "                    if nums[j] != nums[l]:\n",
    "                        dp[mask][j] = min(dp[mask][j], dp[mask^(1<<j)][l] + nums[l] - nums[j])\n",
    "                        \n",
    "        return min(dp[-1]) if min(dp[-1]) != float(\"inf\") else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIncompatibility(self, nums: List[int], k: int) -> int:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if j == u:\n",
    "             return 0\n",
    "          candidate = u ^ j\n",
    "          c = candidate\n",
    "          res = 10 ** 5\n",
    "          while c:\n",
    "             if arr[c] != -1:\n",
    "                res = min(res, dfs(i + 1, j | c) + arr[c])\n",
    "             c = (c - 1) & candidate\n",
    "          return res\n",
    "          \n",
    "       n = len(nums)\n",
    "       cnts = [0] * (n + 1)\n",
    "       u = (1 << n) - 1\n",
    "       for num in nums:\n",
    "          cnts[num] += 1\n",
    "       if max(cnts) > k:\n",
    "          return -1\n",
    "       if n == k:\n",
    "          return 0\n",
    "       arr = [-1] * (1 << n)\n",
    "       for i in range(1 << n):\n",
    "          if i.bit_count() != n // k:\n",
    "             continue\n",
    "          m = 0\n",
    "          flag = False\n",
    "          copy = i\n",
    "          max_val = 0\n",
    "          min_val = n + 1\n",
    "          while copy:\n",
    "             lb = (copy & -copy).bit_length() - 1\n",
    "             if (m >> nums[lb]) & 1:\n",
    "                flag = True\n",
    "                break\n",
    "             m |= 1 << nums[lb]\n",
    "             max_val = max(max_val, nums[lb])\n",
    "             min_val = min(min_val, nums[lb])\n",
    "             copy &= copy - 1\n",
    "          if flag:\n",
    "             continue\n",
    "          arr[i] = max_val - min_val\n",
    "       return dfs(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
